import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MergeSort {
    public static int maxBlock = 20;
    public static int maxRecordPerWay = 60000;
    public static int recordPerBlock = maxRecordPerWay / maxBlock;
    public static int fileCount = 0;
    public static Comparator<Data> comparator = new Comparator<Data>() {
        @Override
        public int compare(Data arg0, Data arg1) {
            int key0 = arg0.key;
            int key1 = arg1.key;
            if (key0 > key1)
                return 1;
            else if (key0 == key1)
                return 0;
            return -1;
        }
    };

    public static void main(String[] args) {
        MergeSort ms = new MergeSort();
        long startTime = System.currentTimeMillis();
        ms.mergeSort();
        long endTime = System.currentTimeMillis();
        System.out.println("共用时" + (endTime - startTime) + "ms");
    }

    /*
     * 内存大小为1m 每条记录16B 故内存最多可以装下65536条记录 据以上数据，设一路有60000条记录，一块有5000条记录，每一路由12块组成。
     * 内存至少装入12块数据 一下实验根据上述假设完成
     */
    public void mergeSort() {
        // 初始化磁盘
        MyFile allRecord = new MyFile("data.txt");
        List<MyFile> ways = new ArrayList<>();
        // 实现分组和分组排序
        List<Data> current = new ArrayList<>();
        int count = 0;
        while (!allRecord.isEnd()) {
            current.addAll(allRecord.readBlock());
            count += 1;
            if (count == MergeSort.maxBlock) {
                count = 0;
                Collections.sort(current, comparator);
                String fileName = this.outputToFile(current);
                fileCount++;
                ways.add(new MyFile(fileName));
                current.clear();
            }
        }
        // 将剩余不足20块的记录归为一路
        if (count != 0) {
            Collections.sort(current, comparator);
            String fileName = this.outputToFile(current);
            fileCount++;
            ways.add(new MyFile(fileName));
            current.clear();
        }
        // 进行归并排序
        while (ways.size() > 1) {
            int emptyWays = 0;
            int numOfMergeWays = Math.min(MergeSort.maxBlock - 2, ways.size());
            int[] wayTag = new int[numOfMergeWays];
            // 设置排序块和输出块和每一路的块
            List<Data> outputBlock = new ArrayList<>();
            List<ArrayList<Data>> inputBlocks = new ArrayList<>(numOfMergeWays);
            Data[] sortBlock = new Data[numOfMergeWays];

            for (int i = 0; i < numOfMergeWays; i++) {
                inputBlocks.add(ways.get(i).readBlock());
                sortBlock[i] = inputBlocks.get(i).remove(0);
                wayTag[i] = 0;
            }

            while (emptyWays < numOfMergeWays) {
                Data min = new Data(Integer.MAX_VALUE, "");
                int index = -1;
                for (int i = 0; i < numOfMergeWays; i++)
                    if (wayTag[i] == 0 && sortBlock[i].key < min.key) {
                        min = sortBlock[i];
                        index = i;
                    }
                outputBlock.add(min);
                if (outputBlock.size() == MergeSort.recordPerBlock) {
                    outputToFile(outputBlock);// 输出到文件
                    outputBlock.clear();
                }
                if (inputBlocks.get(index).isEmpty()) {
                    if (ways.get(index).isEnd()) {
                        emptyWays++;
                        wayTag[index] = 1;
                    } else {
                        inputBlocks.get(index).addAll(ways.get(index).readBlock());
                        sortBlock[index] = inputBlocks.get(index).remove(0);
                    }
                } else {
                    sortBlock[index] = inputBlocks.get(index).remove(0);
                }
            }
            String fileName = outputToFile(outputBlock);// 将剩余的记录输出到文件
            outputBlock.clear();
            fileCount++;
            if (numOfMergeWays > 0) {
                ways.subList(0, numOfMergeWays).clear();
            }
            ways.add(new MyFile(fileName));
        }
        File file = new File((fileCount - 1) + ".txt");
        //System.out.println(file.renameTo(new File("sorted_data.txt")));
    }

    private String outputToFile(List<Data> current) {
        String path = fileCount + ".txt";
        try {
            BufferedWriter bw = new BufferedWriter(new FileWriter(new File(path), true));
            for (Data d : current)
                bw.write(d.key + " " + d.data + "\n");
            bw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return path;
    }
}
